#pragma once
#include <stddef.h>

namespace snow
{

// 给迭代器明确的类型，以便于它选择高效率的算法
struct input_iterator_tag { // 只读，不允许外界改变
};
struct output_iterator_tag { // 只写
};
struct forward_iterator_tag
    : public input_iterator_tag {
};
struct bidirectional_iterator_tag
    : public forward_iterator_tag {
};
struct random_access_iterator_tag
    : public bidirectional_iterator_tag {
};

template <class T, class Distance>
struct input_iterator {
    using iterator_category = input_iterator_tag;
    using value_type = T;
    using difference_type = Distance;
    using pointer = T *;
    using reference = T &;
};

struct output_iterator {
    using iterator_category = output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;
};

template <class T, class Distance>
struct forward_iterator {
    using iterator_category = forward_iterator_tag;
    using value_type = T;
    using difference_type = Distance;
    using pointer = T *;
    using reference = T &;
};

template <class T, class Distance>
struct bidirectional_iterator {
    using iterator_category = bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = Distance;
    using pointer = T *;
    using reference = T &;
};

template <class T, class Distance>
struct random_access_iterator {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = Distance;
    using pointer = T *;
    using reference = T &;
};

// 写程序难免挂一漏万，设计一个迭代器的基类，让新迭代器继承自它
// 后三个模板参数均有默认值，因此新迭代器只需给前两个参数
template <class Category,
          class T,
          class Distance = ptrdiff_t, // long
          class Pointer = T *,
          class Reference = T &>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
};

// traits 编程技法
template <class Iterator>
struct iterator_traits {
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
};
// 偏特化版，裸指针
template <class T>
struct iterator_traits<T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using reference = T &;
};
// 偏特化版，pointer-to-const
// 声明一个无法赋值(因const)的临时变量没什么用，因此其value_type声明为非const型
template <class T>
struct iterator_traits<const T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using reference = T &;
};

// 这个函数可以很方便的决定某个迭代器类型
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator &It)
{
    using category = typename iterator_traits<Iterator>::iterator_category;
    return category();
}
// 这个函数可以很方便的决定某个value_type
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type *
value_type(const Iterator &It)
{
    return static_cast<typename iterator_traits<Iterator>::value_type *>(0);
}
// 这个函数可以很方便的决定某个distance_type
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type *
difference_type(const Iterator &It)
{
    return static_cast<typename iterator_traits<Iterator>::difference_type *>(0);
}

} // end of namespace snow